package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 * <p>
 * 二叉搜索树定义
 * 1.节点最多只能有两个子节点
 * 2.左节点小于父节点 右节点大于父节点
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-21 16:43
 */
public class AX96不同的二叉搜索树 {

    public static void main(String[] args) {


    }

    /**
     * 动态规划  递推
     * 1.改变根节点 根据二叉树特性 将数据分为左右两部分 则左右两部分的笛卡尔积即为其全部可能性
     * 2.根节点可以从1~n 则f(n)的所有可能性为 g(1)+..+g(n)  g(i) = g(i-1)*g(n-i)
     * 3.g(0~i) = f(i)
     *
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        int[] G = new int[n + 1];
        //空树(避免算乘积时 被归0)
        G[0] = 1;
        //一棵数
        G[1] = 1;
        //总数
        for (int i = 2; i <= n; ++i) {
            //根节点值
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }


}
